      1  import java.util.Iterator;

      2  import java.util.NoSuchElementException;

      3

      4  /**

      5     This class implements a hash set using separate chaining.

      6  */

      7  public class HashSet

      8  {

      9     private Node[] buckets;

     10     private int currentSize;

     11

     12     /**

     13        Constructs a hash table.

     14        @param bucketsLength the length of the buckets array

     15     */

     16     public HashSet(int bucketsLength)

     17     {

     18        buckets = new Node[bucketsLength];

     19        currentSize = 0;

     20     }

     21

     22     /**

     23        Tests for set membership.

     24        @param x an object

     25        @return true if x is an element of this set

     26     */

     27     public boolean contains(Object x)

     28     {

     29        int h = x.hashCode();

     30        if (h < 0) { h = -h; }

     31        h = h % buckets.length;

     32

     33        Node current = buckets[h];

     34        while (current != null)

     35        {

     36           if (current.data.equals(x)) { return true; }

     37           current = current.next;

     38        }

     39        return false;

     40     }

     41

     42     /**

     43        Adds an element to this set.

     44        @param x an object

     45        @return true if x is a new object, false if x was

     46        already in the set

     47     */

     48     public boolean add(Object x)

     49     {

     50        int h = x.hashCode();

     51        if (h < 0) { h = -h; }

     52        h = h % buckets.length;

     53

     54        Node current = buckets[h];

     55        while (current != null)

     56        {

     57           if (current.data.equals(x)) { return false; }

     58              // Already in the set

     59           current = current.next;

     60        }

     61        Node newNode = new Node();

     62        newNode.data = x;

     63        newNode.next = buckets[h];

     64        buckets[h] = newNode;

     65        currentSize++;

     66        return true;

     67     }

     68

     69     /**

     70        Removes an object from this set.

     71        @param x an object

     72        @return true if x was removed from this set, false

     73        if x was not an element of this set

     74     */

     75     public boolean remove(Object x)

     76     {

     77        int h = x.hashCode();

     78        if (h < 0) { h = -h; }

     79        h = h % buckets.length;

     80

     81        Node current = buckets[h];

     82        Node previous = null;

     83        while (current != null)

     84        {

     85           if (current.data.equals(x))

     86           {

     87              if (previous == null) { buckets[h] = current.next; }

     88              else { previous.next = current.next; }

     89              currentSize--;

     90              return true;

     91           }

     92           previous = current;

     93           current = current.next;

     94        }

     95        return false;

     96     }

     97

     98     /**

     99        Returns an iterator that traverses the elements of this set.

    100        @return a hash set iterator

    101     */

    102     public Iterator iterator()

    103     {

    104        return new HashSetIterator();

    105     }

    106

    107     /**

    108        Gets the number of elements in this set.

    109        @return the number of elements

    110     */

    111     public int size()

    112     {

    113        return currentSize;

    114     }

    115

    116     class Node

    117     {

    118        public Object data;

    119        public Node next;

    120     }

    121

    122     class HashSetIterator implements Iterator

    123     {

    124        private int bucketIndex;

    125        private Node current;

    126

    127        /**

    128           Constructs a hash set iterator that points to the

    129           first element of the hash set.

    130        */

    131        public HashSetIterator()

    132        {

    133           current = null;

    134           bucketIndex = -1;

    135        }

    136

    137        public boolean hasNext()

    138        {

    139           if (current != null && current.next != null) { return true; }

    140           for (int b = bucketIndex + 1; b < buckets.length; b++)

    141           {

    142              if (buckets[b] != null) { return true; }

    143           }

    144           return false;

    145        }

    146

    147        public Object next()

    148        {

    149           if (current != null && current.next != null)

    150           {

    151              current = current.next; // Move to next element in bucket

    152           }

    153           else // Move to next bucket

    154           {

    155              do

    156              {

    157                 bucketIndex++;

    158                 if (bucketIndex == buckets.length)

    159                 {

    160                    throw new NoSuchElementException();

    161                 }

    162                 current = buckets[bucketIndex];

    163              }

    164              while (current == null);

    165           }

    166           return current.data;

    167        }

    168

    169        public void remove()

    170        {

    171           throw new UnsupportedOperationException();

    172        }

    173     }

    174  }